package com.yupi.yupao.utils;

import java.util.List;
/**
 * 算法工具类
 */

/**
 * @Author FengHuan Wang
 * @Date 2025/4/11 14:13
 * @Version 1.0
 */
public class AlgorithmUtil {


    /**
     * 计算两个字符串集合的编辑距离
     * @param list1
     * @param list2
     * @return
     */
    public static int calculateEditDistance(List<String> list1, List<String> list2) {
        int m = list1.size();
        int n = list2.size();

        // 创建一个二维数组存储子问题的解
        int[][] dp = new int[m + 1][n + 1];

        // 初始化边界条件
        for (int i = 0; i <= m; i++) {
            // 删除操作
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            // 插入操作
            dp[0][j] = j;
        }

        // 动态规划填表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (list1.get(i - 1).equals(list2.get(j - 1))) {
                    // 字符匹配，无需操作
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(
                            // 插入或删除
                            Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1),
                            // 替换
                            dp[i - 1][j - 1] + 1
                    );
                }
            }
        }

        // 返回最终结果
        return dp[m][n];
    }


    /**
     * 计算相似度
     * @param list1
     * @param list2
     * @return
     */
    public static double calculateSimilarity(List<String> list1, List<String> list2) {
        int editDistance = calculateEditDistance(list1, list2);
        int maxLength = Math.max(list1.size(), list2.size());
        // 相似度公式
        return 1.0 - (double) editDistance / maxLength;
    }
}
